#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    void dfs(int u, vector<vector<int>>& g, int n, vector<vector<int>>& ans, vector<int>& p) {
        if (u == n - 1) {
            ans.push_back(p);
            return;
        }
        // p.push_back(u);
        if (u == 0)p.push_back(u);
        for (auto it : g[u]) {
            p.push_back(it);
            dfs(it, g, n, ans, p);
            p.pop_back();
        }
        // p.pop_back();
    }
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<int>> g(n);
        vector<vector<int>> ans;
        vector<int> dist(n);
        // g[0].push_back(0);
        for (int i = 0; i < n; i++) {
            for (auto it : graph[i]) {
                g[i].push_back(it);
            }
        }

        vector<int> p;
        dfs(0, g, n, ans, p);
        return ans;
    }
};